题解 洛谷 P5686 [CSP-S2019 江西] 和积和

P5686 [CSP-S2019 江西] 和积和

简要题意

给定两个 $n$ 个元素的序列 $a,b$，求下面这个式子对 $10^9+7$ 取模的结果：
$$
\sum_{l=1}^{n}\sum_{r=l}^{n}(\sum_{i=l}^{r}a_i \times \sum_{i=l}^{r}b_i)
$$

策略分析

如果直接模拟那么时间复杂度是爆炸级的 $O(n^3)$，显然正常人都不会这么做，正常人会选择可爱的前缀和，所以最后一层括号复杂度变成 $O(1)$，总复杂度 $O(n^2)$，比刚刚好了很多，但依然是过不去的，所以我们考虑对前缀和进行优化。

设 $a$ 的前缀数组为 $A$，$b$ 的前缀数组为 $B$。那么上面的式子显然可以写成：
$$
\sum_{l=1}^{n}\sum_{r=l}^n(A_r-A_{l-1})(B_r-B_{l-1}) \
=\sum_{l=1}^{n}\sum_{r=l}^n(A_rB_r+A_{l-1}B_{r-1}-A_rB_{l-1}-A_{l-1}B_r)
$$
这样看我们求解还不是很方便，因为存在前面的求和符号，我们不便于对整体的式子进行观察，所以我们用一个 $n$ 较小的式子看一下，比方说令 $n=4$，那么我们按照这个式子带进去展开化简得到：
$$
sum=4(A_1B_1+A_2B_2+A_3B_3+A_4B_4) \
-(A_1B_2+A_1B_3+A_1B_4+A_2B_1+A_2B_3+A_2B_4 \
+A_3B_1+A_3B_2+A_3B_4+A_4B_1+A_4B_2+A_4B_3)
$$
那么前面系数为 $4$ 的那个式子我们就可以 $O(n)$ 求了，关键转移到了如何求后面这一坨东西。我们把 $A$ 和 $B$ 按照下标放到矩阵里看一看：
$$
\begin{bmatrix}
0& A_1B_2& A_1B_3& A_1B_4\
A_2B_1& 0& A_2B_3& A_2B_4\
A_3B_1& A_3B_2& 0& A_3B_4\
A_4B_1& A_4B_2& A_4B_3& 0
\end{bmatrix}
$$
我们发现这不就是 $A$ 每一项去乘 $B$ 每一项吗，唯一的遗憾是对角线全是 $0$。我们期望能够对这个式子进行因式分解使其变成两个只包含 $A$ 或 $B$ 的式子相乘，那么其实想办法把这个对角线给它补齐就行了，我们发现对角线的 $A,B$ 下标相等，那么就和刚刚系数为 $4$ 的那个式子一模一样了，所以我们在这多减一遍，前面多加一遍，整个式子的值不变，式子变成这样：
$$
sum=5 \times \sum_{i=1}^{4}A_iB_i-(\sum_{i=1}^4A_i \times \sum_{i=1}^4B_i)
$$
然后把这个结论归纳到 $n$ 项得：
$$
\begin{aligned}
sum=(n+1) \times \sum_{i=1}^{n}A_iB_i-(\sum_{i=1}^{n}A_i \times \sum_{i=1}^{n}B_i) \
=\sum_{i=1}^{n}(n+1)\times A_iB_i-(\sum_{i=1}^{n}A_i \times \sum_{i=1}^{n}B_i)
\end{aligned}
$$
图中三个求和符不存在嵌套，所以每一个都可以拿出来单独计算，时间复杂度降低到了 $O(n)$，于是这道题就做完了。做题的时候要注意，本题给定的数都特别大，所以在求解的过程中不要忘记时刻取模。

参考代码

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

namespace SHAWN {
    const LL N = 5e5 + 7, mod = 1e9 + 7;
    LL n, ans, A, B;
    LL a[N], b[N];
    int work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) { 
            cin >> a[i];
            a[i] = (a[i] + a[i - 1]) % mod;// 求a的前缀
        }
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
            b[i] = (b[i] + b[i - 1]) % mod;// 求b的前缀
        }
        for (int i = 1; i <= n; ++i) {
            ans = (ans % mod + ((n + 1) * a[i]) % mod * b[i] % mod) % mod;
            // 处理第一个求和符
            A = (A + a[i]) % mod;
            // 处理第二个求和符
            B = (B + b[i]) % mod;
            // 处理第三个求和符
        }
        ans = ((ans - (A * B % mod)) + mod) % mod;
        // 将三个求和符号按照推出来的式子加到一块
        cout << ans % mod << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}